Constrained subsequence sum [Sliding Window Maximum]

Time: O(N); Space: O(K); hard

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2

Output: 37

Explanation:

  • The subsequence is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1

Output: -1

Explanation:

  • The subsequence must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2

Output: 23

Explanation:

  • The subsequence is [10, -2, -5, 20].

Constraints:

  • 1 <= k <= len(nums) <= 10^5

  • -10^4 <= nums[i] <= 10^4

[1]:

import collections

class Solution1(object):
    """
    Time: O(N)
    Space: O(K)
    """
    def constrainedSubsetSum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        result, dq = float("-inf"), collections.deque()

        for i in range(len(nums)):
            if dq and i-dq[0][0] == k+1:
                dq.popleft()

            curr = nums[i] + (dq[0][1] if dq else 0)

            while dq and dq[-1][1] <= curr:
                dq.pop()
            if curr > 0:
                dq.append((i, curr))
            result = max(result, curr)

        return result

Hints:

  1. Use dynamic programming.

  2. Let dp[i] be the solution for the prefix of the array that ends at index i, if the element at index i is in the subsequence.

  3. dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], …, dp[i-1])

  4. Use a heap with the sliding window technique to optimize the dp.

[2]:

s = Solution1()

nums = [10,2,-10,5,20]
k = 2
assert s.constrainedSubsetSum(nums, k) == 37

nums = [-1,-2,-3]
k = 1
assert s.constrainedSubsetSum(nums, k) == -1

nums = [10,-2,-10,-5,20]
k = 2
assert s.constrainedSubsetSum(nums, k) == 23